/**********
This library is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the
Free Software Foundation; either version 3 of the License, or (at your
option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)

This library is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
more details.

You should have received a copy of the GNU Lesser General Public License
along with this library; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
**********/
// "liveMedia"
// Copyright (c) 1996-2018 Live Networks, Inc.  All rights reserved.
// A filter that produces a sequence of I-frame indices from a MPEG-2 Transport Stream
// Implementation

#include "include/MPEG2IndexFromTransportStream.hh"

////////// IndexRecord definition //////////

enum RecordType {
    RECORD_UNPARSED = 0,
    RECORD_VSH = 1, // a MPEG Video Sequence Header
    RECORD_GOP = 2,
    RECORD_PIC_NON_IFRAME = 3, // includes slices
    RECORD_PIC_IFRAME = 4, // includes slices
    RECORD_NAL_H264_SPS = 5, // H.264
    RECORD_NAL_H264_PPS = 6, // H.264
    RECORD_NAL_H264_SEI = 7, // H.264
    RECORD_NAL_H264_NON_IFRAME = 8, // H.264
    RECORD_NAL_H264_IFRAME = 9, // H.264
    RECORD_NAL_H264_OTHER = 10, // H.264
    RECORD_NAL_H265_VPS = 11, // H.265
    RECORD_NAL_H265_SPS = 12, // H.265
    RECORD_NAL_H265_PPS = 13, // H.265
    RECORD_NAL_H265_NON_IFRAME = 14, // H.265
    RECORD_NAL_H265_IFRAME = 15, // H.265
    RECORD_NAL_H265_OTHER = 16, // H.265
    RECORD_JUNK
};

class IndexRecord {
public:
    IndexRecord(u_int8_t startOffset, u_int8_t size,
                unsigned long transportPacketNumber, float pcr);

    virtual ~IndexRecord();

    RecordType &recordType() { return fRecordType; }

    void setFirstFlag() { fRecordType = (RecordType) (((u_int8_t) fRecordType) | 0x80); }

    u_int8_t startOffset() const { return fStartOffset; }

    u_int8_t &size() { return fSize; }

    float pcr() const { return fPCR; }

    unsigned long transportPacketNumber() const { return fTransportPacketNumber; }

    IndexRecord *next() const { return fNext; }

    void addAfter(IndexRecord *prev);

    void unlink();

private:
    // Index records are maintained in a doubly-linked list:
    IndexRecord *fNext;
    IndexRecord *fPrev;

    RecordType fRecordType;
    u_int8_t fStartOffset; // within the Transport Stream packet
    u_int8_t fSize; // in bytes, following "fStartOffset".
    // Note: fStartOffset + fSize <= TRANSPORT_PACKET_SIZE
    float fPCR;
    unsigned long fTransportPacketNumber;
};

#ifdef DEBUG
static char const* recordTypeStr[] = {
  "UNPARSED",
  "VSH",
  "GOP",
  "PIC(non-I-frame)",
  "PIC(I-frame)",
  "SPS (H.264)",
  "PPS (H.264)",
  "SEI (H.264)",
  "H.264 non-I-frame",
  "H.264 I-frame",
  "other NAL unit (H.264)",
  "VPS (H.265)",
  "SPS (H.265)",
  "PPS (H.265)",
  "H.265 non-I-frame",
  "H.265 I-frame",
  "other NAL unit (H.265)",
  "JUNK"
};

UsageEnvironment& operator<<(UsageEnvironment& env, IndexRecord& r) {
  return env << "[" << ((r.recordType()&0x80) != 0 ? "1" : "")
         << recordTypeStr[r.recordType()&0x7F] << ":"
         << (unsigned)r.transportPacketNumber() << ":" << r.startOffset()
         << "(" << r.size() << ")@" << r.pcr() << "]";
}
#endif


////////// MPEG2IFrameIndexFromTransportStream implementation //////////

MPEG2IFrameIndexFromTransportStream *
MPEG2IFrameIndexFromTransportStream::createNew(UsageEnvironment &env,
                                               FramedSource *inputSource) {
    return new MPEG2IFrameIndexFromTransportStream(env, inputSource);
}

// The largest expected frame size (in bytes):
#define MAX_FRAME_SIZE 400000

// Make our parse buffer twice as large as this, to ensure that at least one
// complete frame will fit inside it:
#define PARSE_BUFFER_SIZE (2*MAX_FRAME_SIZE)

// The PID used for the PAT (as defined in the MPEG Transport Stream standard):
#define PAT_PID 0

MPEG2IFrameIndexFromTransportStream
::MPEG2IFrameIndexFromTransportStream(UsageEnvironment &env,
                                      FramedSource *inputSource)
        : FramedFilter(env, inputSource),
          fIsH264(False), fIsH265(False),
          fInputTransportPacketCounter((unsigned) -1), fClosureNumber(0),
          fLastContinuityCounter(~0),
          fFirstPCR(0.0), fLastPCR(0.0), fHaveSeenFirstPCR(False),
          fPMT_PID(0x10), fVideo_PID(0xE0), // default values
          fParseBufferSize(PARSE_BUFFER_SIZE),
          fParseBufferFrameStart(0), fParseBufferParseEnd(4), fParseBufferDataEnd(0),
          fHeadIndexRecord(NULL), fTailIndexRecord(NULL) {
    fParseBuffer = new unsigned char[fParseBufferSize];
}

MPEG2IFrameIndexFromTransportStream::~MPEG2IFrameIndexFromTransportStream() {
    delete fHeadIndexRecord;
    delete[] fParseBuffer;
}

void MPEG2IFrameIndexFromTransportStream::doGetNextFrame() {
    // Begin by trying to deliver an index record (for an already-parsed frame)
    // to the client:
    if (deliverIndexRecord()) return;

    // No more index records are left to deliver, so try to parse a new frame:
    if (parseFrame()) { // success - try again
        doGetNextFrame();
        return;
    }

    // We need to read some more Transport Stream packets.  Check whether we have room:
    if (fParseBufferSize - fParseBufferDataEnd < TRANSPORT_PACKET_SIZE) {
        // There's no room left.  Compact the buffer, and check again:
        compactParseBuffer();
        if (fParseBufferSize - fParseBufferDataEnd < TRANSPORT_PACKET_SIZE) {
            envir() << "ERROR: parse buffer full; increase MAX_FRAME_SIZE\n";
            // Treat this as if the input source ended:
            handleInputClosure1();
            return;
        }
    }

    // Arrange to read a new Transport Stream packet:
    fInputSource->getNextFrame(fInputBuffer, sizeof fInputBuffer,
                               afterGettingFrame, this,
                               handleInputClosure, this);
}

void MPEG2IFrameIndexFromTransportStream
::afterGettingFrame(void *clientData, unsigned frameSize,
                    unsigned numTruncatedBytes,
                    struct timeval presentationTime,
                    unsigned durationInMicroseconds) {
    MPEG2IFrameIndexFromTransportStream *source
            = (MPEG2IFrameIndexFromTransportStream *) clientData;
    source->afterGettingFrame1(frameSize, numTruncatedBytes,
                               presentationTime, durationInMicroseconds);
}

#define TRANSPORT_SYNC_BYTE 0x47

void MPEG2IFrameIndexFromTransportStream
::afterGettingFrame1(unsigned frameSize,
                     unsigned numTruncatedBytes,
                     struct timeval presentationTime,
                     unsigned durationInMicroseconds) {
    if (frameSize < TRANSPORT_PACKET_SIZE || fInputBuffer[0] != TRANSPORT_SYNC_BYTE) {
        if (fInputBuffer[0] != TRANSPORT_SYNC_BYTE) {
            envir() << "Bad TS sync byte: 0x" << fInputBuffer[0] << "\n";
        }
        // Handle this as if the source ended:
        handleInputClosure1();
        return;
    }

    ++fInputTransportPacketCounter;

    // Figure out how much of this Transport Packet contains PES data:
    u_int8_t adaptation_field_control = (fInputBuffer[3] & 0x30) >> 4;
    u_int8_t totalHeaderSize
            = adaptation_field_control <= 1 ? 4 : 5 + fInputBuffer[4];
    if ((adaptation_field_control == 2 && totalHeaderSize != TRANSPORT_PACKET_SIZE) ||
        (adaptation_field_control == 3 && totalHeaderSize >= TRANSPORT_PACKET_SIZE)) {
        envir() << "Bad \"adaptation_field_length\": " << fInputBuffer[4] << "\n";
        doGetNextFrame();
        return;
    }

    // Check for a PCR:
    if (totalHeaderSize > 5 && (fInputBuffer[5] & 0x10) != 0) {
        // There's a PCR:
        u_int32_t pcrBaseHigh
                = (fInputBuffer[6] << 24) | (fInputBuffer[7] << 16)
                  | (fInputBuffer[8] << 8) | fInputBuffer[9];
        float pcr = pcrBaseHigh / 45000.0f;
        if ((fInputBuffer[10] & 0x80) != 0) pcr += 1 / 90000.0f; // add in low-bit (if set)
        unsigned short pcrExt = ((fInputBuffer[10] & 0x01) << 8) | fInputBuffer[11];
        pcr += pcrExt / 27000000.0f;

        if (!fHaveSeenFirstPCR) {
            fFirstPCR = pcr;
            fHaveSeenFirstPCR = True;
        } else if (pcr < fLastPCR) {
            // The PCR timestamp has gone backwards.  Display a warning about this
            // (because it indicates buggy Transport Stream data), and compensate for it.
            envir() << "\nWarning: At about " << fLastPCR - fFirstPCR
                    << " seconds into the file, the PCR timestamp decreased - from "
                    << fLastPCR << " to " << pcr << "\n";
            fFirstPCR -= (fLastPCR - pcr);
        }
        fLastPCR = pcr;
    }

    // Get the PID from the packet, and check for special tables: the PAT and PMT:
    u_int16_t PID = ((fInputBuffer[1] & 0x1F) << 8) | fInputBuffer[2];
    if (PID == PAT_PID) {
        analyzePAT(&fInputBuffer[totalHeaderSize], TRANSPORT_PACKET_SIZE - totalHeaderSize);
    } else if (PID == fPMT_PID) {
        analyzePMT(&fInputBuffer[totalHeaderSize], TRANSPORT_PACKET_SIZE - totalHeaderSize);
    }

    // Ignore transport packets for non-video programs,
    // or packets with no data, or packets that duplicate the previous packet:
    u_int8_t continuity_counter = fInputBuffer[3] & 0x0F;
    if ((PID != fVideo_PID) ||
        !(adaptation_field_control == 1 || adaptation_field_control == 3) ||
        continuity_counter == fLastContinuityCounter) {
        doGetNextFrame();
        return;
    }
    fLastContinuityCounter = continuity_counter;

    // Also, if this is the start of a PES packet, then skip over the PES header:
    Boolean payload_unit_start_indicator = (fInputBuffer[1] & 0x40) != 0;
    if (payload_unit_start_indicator && totalHeaderSize < TRANSPORT_PACKET_SIZE - 8
        && fInputBuffer[totalHeaderSize] == 0x00 && fInputBuffer[totalHeaderSize + 1] == 0x00
        && fInputBuffer[totalHeaderSize + 2] == 0x01) {
        u_int8_t PES_header_data_length = fInputBuffer[totalHeaderSize + 8];
        totalHeaderSize += 9 + PES_header_data_length;
        if (totalHeaderSize >= TRANSPORT_PACKET_SIZE) {
            envir() << "Unexpectedly large PES header size: " << PES_header_data_length << "\n";
            // Handle this as if the source ended:
            handleInputClosure1();
            return;
        }
    }

    // The remaining data is Video Elementary Stream data.  Add it to our parse buffer:
    unsigned vesSize = TRANSPORT_PACKET_SIZE - totalHeaderSize;
    memmove(&fParseBuffer[fParseBufferDataEnd], &fInputBuffer[totalHeaderSize], vesSize);
    fParseBufferDataEnd += vesSize;

    // And add a new index record noting where it came from:
    addToTail(new IndexRecord(totalHeaderSize, vesSize, fInputTransportPacketCounter,
                              fLastPCR - fFirstPCR));

    // Try again:
    doGetNextFrame();
}

void MPEG2IFrameIndexFromTransportStream::handleInputClosure(void *clientData) {
    MPEG2IFrameIndexFromTransportStream *source
            = (MPEG2IFrameIndexFromTransportStream *) clientData;
    source->handleInputClosure1();
}

#define VIDEO_SEQUENCE_START_CODE 0xB3        // MPEG-1 or 2
#define VISUAL_OBJECT_SEQUENCE_START_CODE 0xB0    // MPEG-4
#define GROUP_START_CODE 0xB8            // MPEG-1 or 2
#define GROUP_VOP_START_CODE 0xB3        // MPEG-4
#define PICTURE_START_CODE 0x00            // MPEG-1 or 2
#define VOP_START_CODE 0xB6            // MPEG-4

void MPEG2IFrameIndexFromTransportStream::handleInputClosure1() {
    if (++fClosureNumber == 1 && fParseBufferDataEnd > fParseBufferFrameStart
        && fParseBufferDataEnd <= fParseBufferSize - 4) {
        // This is the first time we saw EOF, and there's still data remaining to be
        // parsed.  Hack: Append a Picture Header code to the end of the unparsed
        // data, and try again.  This should use up all of the unparsed data.
        fParseBuffer[fParseBufferDataEnd++] = 0;
        fParseBuffer[fParseBufferDataEnd++] = 0;
        fParseBuffer[fParseBufferDataEnd++] = 1;
        fParseBuffer[fParseBufferDataEnd++] = PICTURE_START_CODE;

        // Try again:
        doGetNextFrame();
    } else {
        // Handle closure in the regular way:
        handleClosure();
    }
}

void MPEG2IFrameIndexFromTransportStream
::analyzePAT(unsigned char *pkt, unsigned size) {
    // Get the PMT_PID:
    while (size >= 17) { // The table is large enough
        u_int16_t program_number = (pkt[9] << 8) | pkt[10];
        if (program_number != 0) {
            fPMT_PID = ((pkt[11] & 0x1F) << 8) | pkt[12];
            return;
        }

        pkt += 4;
        size -= 4;
    }
}

void MPEG2IFrameIndexFromTransportStream
::analyzePMT(unsigned char *pkt, unsigned size) {
    // Scan the "elementary_PID"s in the map, until we see the first video stream.

    // First, get the "section_length", to get the table's size:
    u_int16_t section_length = ((pkt[2] & 0x0F) << 8) | pkt[3];
    if ((unsigned) (4 + section_length) < size) size = (4 + section_length);

    // Then, skip any descriptors following the "program_info_length":
    if (size < 22) return; // not enough data
    unsigned program_info_length = ((pkt[11] & 0x0F) << 8) | pkt[12];
    pkt += 13;
    size -= 13;
    if (size < program_info_length) return; // not enough data
    pkt += program_info_length;
    size -= program_info_length;

    // Look at each ("stream_type","elementary_PID") pair, looking for a video stream:
    while (size >= 9) {
        u_int8_t stream_type = pkt[0];
        u_int16_t elementary_PID = ((pkt[1] & 0x1F) << 8) | pkt[2];
        if (stream_type == 1 || stream_type == 2 ||
            stream_type == 0x1B/*H.264 video*/ || stream_type == 0x24/*H.265 video*/) {
            if (stream_type == 0x1B) fIsH264 = True;
            else if (stream_type == 0x24) fIsH265 = True;
            fVideo_PID = elementary_PID;
            return;
        }

        u_int16_t ES_info_length = ((pkt[3] & 0x0F) << 8) | pkt[4];
        pkt += 5;
        size -= 5;
        if (size < ES_info_length) return; // not enough data
        pkt += ES_info_length;
        size -= ES_info_length;
    }
}

Boolean MPEG2IFrameIndexFromTransportStream::deliverIndexRecord() {
    IndexRecord *head = fHeadIndexRecord;
    if (head == NULL) return False;

    // Check whether the head record has been parsed yet:
    if (head->recordType() == RECORD_UNPARSED) return False;

    // Remove the head record (the one whose data we'll be delivering):
    IndexRecord *next = head->next();
    head->unlink();
    if (next == head) {
        fHeadIndexRecord = fTailIndexRecord = NULL;
    } else {
        fHeadIndexRecord = next;
    }

    if (head->recordType() == RECORD_JUNK) {
        // Don't actually deliver the data to the client:
        delete head;
        // Try to deliver the next record instead:
        return deliverIndexRecord();
    }

    // Deliver data from the head record:
#ifdef DEBUG
    envir() << "delivering: " << *head << "\n";
#endif
    if (fMaxSize < 11) {
        fFrameSize = 0;
    } else {
        fTo[0] = (u_int8_t) (head->recordType());
        fTo[1] = head->startOffset();
        fTo[2] = head->size();
        // Deliver the PCR, as 24 bits (integer part; little endian) + 8 bits (fractional part)
        float pcr = head->pcr();
        unsigned pcr_int = (unsigned) pcr;
        u_int8_t pcr_frac = (u_int8_t) (256 * (pcr - pcr_int));
        fTo[3] = (unsigned char) (pcr_int);
        fTo[4] = (unsigned char) (pcr_int >> 8);
        fTo[5] = (unsigned char) (pcr_int >> 16);
        fTo[6] = (unsigned char) (pcr_frac);
        // Deliver the transport packet number (in little-endian order):
        unsigned long tpn = head->transportPacketNumber();
        fTo[7] = (unsigned char) (tpn);
        fTo[8] = (unsigned char) (tpn >> 8);
        fTo[9] = (unsigned char) (tpn >> 16);
        fTo[10] = (unsigned char) (tpn >> 24);
        fFrameSize = 11;
    }

    // Free the (former) head record (as we're now done with it):
    delete head;

    // Complete delivery to the client:
    afterGetting(this);
    return True;
}

Boolean MPEG2IFrameIndexFromTransportStream::parseFrame() {
    // At this point, we have a queue of >=0 (unparsed) index records, representing
    // the data in the parse buffer from "fParseBufferFrameStart"
    // to "fParseBufferDataEnd".  We now parse through this data, looking for
    // a complete 'frame', where a 'frame', in this case, means:
    // 	for MPEG video: a Video Sequence Header, GOP Header, Picture Header, or Slice
    // 	for H.264 or H.265 video: a NAL unit

    // Inspect the frame's initial 4-byte code, to make sure it starts with a system code:
    if (fParseBufferDataEnd - fParseBufferFrameStart < 4) return False; // not enough data
    unsigned numInitialBadBytes = 0;
    unsigned char const *p = &fParseBuffer[fParseBufferFrameStart];
    if (!(p[0] == 0 && p[1] == 0 && p[2] == 1)) {
        // There's no system code at the beginning.  Parse until we find one:
        if (fParseBufferParseEnd == fParseBufferFrameStart + 4) {
            // Start parsing from the beginning of the frame data:
            fParseBufferParseEnd = fParseBufferFrameStart;
        }
        unsigned char nextCode;
        if (!parseToNextCode(nextCode)) return False;

        numInitialBadBytes = fParseBufferParseEnd - fParseBufferFrameStart;
        fParseBufferFrameStart = fParseBufferParseEnd;
        fParseBufferParseEnd += 4; // skip over the code that we just saw
        p = &fParseBuffer[fParseBufferFrameStart];
    }

    unsigned char curCode = p[3];
    if (fIsH264) curCode &= 0x1F; // nal_unit_type
    else if (fIsH265) curCode = (curCode & 0x7E) >> 1;

    RecordType curRecordType;
    unsigned char nextCode;
    if (fIsH264) {
        switch (curCode) {
            case 1: // Coded slice of a non-IDR picture
                curRecordType = RECORD_NAL_H264_NON_IFRAME;
                if (!parseToNextCode(nextCode)) return False;
                break;
            case 5: // Coded slice of an IDR picture
                curRecordType = RECORD_NAL_H264_IFRAME;
                if (!parseToNextCode(nextCode)) return False;
                break;
            case 6: // Supplemental enhancement information (SEI)
                curRecordType = RECORD_NAL_H264_SEI;
                if (!parseToNextCode(nextCode)) return False;
                break;
            case 7: // Sequence parameter set (SPS)
                curRecordType = RECORD_NAL_H264_SPS;
                if (!parseToNextCode(nextCode)) return False;
                break;
            case 8: // Picture parameter set (PPS)
                curRecordType = RECORD_NAL_H264_PPS;
                if (!parseToNextCode(nextCode)) return False;
                break;
            default:
                curRecordType = RECORD_NAL_H264_OTHER;
                if (!parseToNextCode(nextCode)) return False;
                break;
        }
    } else if (fIsH265) {
        switch (curCode) {
            case 19: // Coded slice segment of an IDR picture
            case 20: // Coded slice segment of an IDR picture
                curRecordType = RECORD_NAL_H265_IFRAME;
                if (!parseToNextCode(nextCode)) return False;
                break;
            case 32: // Video parameter set (VPS)
                curRecordType = RECORD_NAL_H265_VPS;
                if (!parseToNextCode(nextCode)) return False;
                break;
            case 33: // Sequence parameter set (SPS)
                curRecordType = RECORD_NAL_H265_SPS;
                if (!parseToNextCode(nextCode)) return False;
                break;
            case 34: // Picture parameter set (PPS)
                curRecordType = RECORD_NAL_H265_PPS;
                if (!parseToNextCode(nextCode)) return False;
                break;
            default:
                curRecordType = (curCode <= 31) ? RECORD_NAL_H265_NON_IFRAME
                                                : RECORD_NAL_H265_OTHER;
                if (!parseToNextCode(nextCode)) return False;
                break;
        }
    } else { // MPEG-1, 2, or 4
        switch (curCode) {
            case VIDEO_SEQUENCE_START_CODE:
            case VISUAL_OBJECT_SEQUENCE_START_CODE:
                curRecordType = RECORD_VSH;
                while (1) {
                    if (!parseToNextCode(nextCode)) return False;
                    if (nextCode == GROUP_START_CODE ||
                        nextCode == PICTURE_START_CODE || nextCode == VOP_START_CODE)
                        break;
                    fParseBufferParseEnd += 4; // skip over the code that we just saw
                }
                break;
            case GROUP_START_CODE:
                curRecordType = RECORD_GOP;
                while (1) {
                    if (!parseToNextCode(nextCode)) return False;
                    if (nextCode == PICTURE_START_CODE || nextCode == VOP_START_CODE) break;
                    fParseBufferParseEnd += 4; // skip over the code that we just saw
                }
                break;
            default: // picture
                curRecordType = RECORD_PIC_NON_IFRAME; // may get changed to IFRAME later
                while (1) {
                    if (!parseToNextCode(nextCode)) return False;
                    if (nextCode == VIDEO_SEQUENCE_START_CODE ||
                        nextCode == VISUAL_OBJECT_SEQUENCE_START_CODE ||
                        nextCode == GROUP_START_CODE || nextCode == GROUP_VOP_START_CODE ||
                        nextCode == PICTURE_START_CODE || nextCode == VOP_START_CODE)
                        break;
                    fParseBufferParseEnd += 4; // skip over the code that we just saw
                }
                break;
        }
    }

    if (curRecordType == RECORD_PIC_NON_IFRAME) {
        if (curCode == VOP_START_CODE) { // MPEG-4
            if ((fParseBuffer[fParseBufferFrameStart + 4] & 0xC0) == 0) {
                // This is actually an I-frame.  Note it as such:
                curRecordType = RECORD_PIC_IFRAME;
            }
        } else { // MPEG-1 or 2
            if ((fParseBuffer[fParseBufferFrameStart + 5] & 0x38) == 0x08) {
                // This is actually an I-frame.  Note it as such:
                curRecordType = RECORD_PIC_IFRAME;
            }
        }
    }

    // There is now a parsed 'frame', from "fParseBufferFrameStart"
    // to "fParseBufferParseEnd". Tag the corresponding index records to note this:
    unsigned frameSize = fParseBufferParseEnd - fParseBufferFrameStart + numInitialBadBytes;
#ifdef DEBUG
    envir() << "parsed " << recordTypeStr[curRecordType] << "; length "
        << frameSize << "\n";
#endif
    for (IndexRecord *r = fHeadIndexRecord;; r = r->next()) {
        if (numInitialBadBytes >= r->size()) {
            r->recordType() = RECORD_JUNK;
            numInitialBadBytes -= r->size();
        } else {
            r->recordType() = curRecordType;
        }
        if (r == fHeadIndexRecord) r->setFirstFlag();
        // indicates that this is the first record for this frame

        if (r->size() > frameSize) {
            // This record contains extra data that's not part of the frame.
            // Shorten this record, and move the extra data to a new record
            // that comes afterwards:
            u_int8_t newOffset = r->startOffset() + frameSize;
            u_int8_t newSize = r->size() - frameSize;
            r->size() = frameSize;
#ifdef DEBUG
            envir() << "tagged record (modified): " << *r << "\n";
#endif

            IndexRecord *newRecord
                    = new IndexRecord(newOffset, newSize, r->transportPacketNumber(), r->pcr());
            newRecord->addAfter(r);
            if (fTailIndexRecord == r) fTailIndexRecord = newRecord;
#ifdef DEBUG
            envir() << "added extra record: " << *newRecord << "\n";
#endif
        } else {
#ifdef DEBUG
            envir() << "tagged record: " << *r << "\n";
#endif
        }
        frameSize -= r->size();
        if (frameSize == 0) break;
        if (r == fTailIndexRecord) { // this shouldn't happen
            envir() << "!!!!!Internal consistency error!!!!!\n";
            return False;
        }
    }

    // Finally, update our parse state (to skip over the now-parsed data):
    fParseBufferFrameStart = fParseBufferParseEnd;
    fParseBufferParseEnd += 4; // to skip over the next code (that we found)

    return True;
}

Boolean MPEG2IFrameIndexFromTransportStream
::parseToNextCode(unsigned char &nextCode) {
    unsigned char const *p = &fParseBuffer[fParseBufferParseEnd];
    unsigned char const *end = &fParseBuffer[fParseBufferDataEnd];
    while (p <= end - 4) {
        if (p[2] > 1) p += 3; // common case (optimized)
        else if (p[2] == 0) ++p;
        else if (p[0] == 0 && p[1] == 0) { // && p[2] == 1
            // We found a code here:
            nextCode = p[3];
            fParseBufferParseEnd = p - &fParseBuffer[0]; // where we've gotten to
            return True;
        } else p += 3;
    }

    fParseBufferParseEnd = p - &fParseBuffer[0]; // where we've gotten to
    return False; // no luck this time
}

void MPEG2IFrameIndexFromTransportStream::compactParseBuffer() {
#ifdef DEBUG
    envir() << "Compacting parse buffer: [" << fParseBufferFrameStart
        << "," << fParseBufferParseEnd << "," << fParseBufferDataEnd << "]";
#endif
    memmove(&fParseBuffer[0], &fParseBuffer[fParseBufferFrameStart],
            fParseBufferDataEnd - fParseBufferFrameStart);
    fParseBufferDataEnd -= fParseBufferFrameStart;
    fParseBufferParseEnd -= fParseBufferFrameStart;
    fParseBufferFrameStart = 0;
#ifdef DEBUG
    envir() << "-> [" << fParseBufferFrameStart
        << "," << fParseBufferParseEnd << "," << fParseBufferDataEnd << "]\n";
#endif
}

void MPEG2IFrameIndexFromTransportStream::addToTail(IndexRecord *newIndexRecord) {
#ifdef DEBUG
    envir() << "adding new: " << *newIndexRecord << "\n";
#endif
    if (fTailIndexRecord == NULL) {
        fHeadIndexRecord = fTailIndexRecord = newIndexRecord;
    } else {
        newIndexRecord->addAfter(fTailIndexRecord);
        fTailIndexRecord = newIndexRecord;
    }
}

////////// IndexRecord implementation //////////

IndexRecord::IndexRecord(u_int8_t startOffset, u_int8_t size,
                         unsigned long transportPacketNumber, float pcr)
        : fNext(this), fPrev(this), fRecordType(RECORD_UNPARSED),
          fStartOffset(startOffset), fSize(size),
          fPCR(pcr), fTransportPacketNumber(transportPacketNumber) {
}

IndexRecord::~IndexRecord() {
    IndexRecord *nextRecord = next();
    unlink();
    if (nextRecord != this) delete nextRecord;
}

void IndexRecord::addAfter(IndexRecord *prev) {
    fNext = prev->fNext;
    fPrev = prev;
    prev->fNext->fPrev = this;
    prev->fNext = this;
}

void IndexRecord::unlink() {
    fNext->fPrev = fPrev;
    fPrev->fNext = fNext;
    fNext = fPrev = this;
}
